#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#include <map>
#include <string>
#include <assert.h>

using namespace std;

#define number double

#define double_zero(n) (((*(((int*)&(n))+1)) & 0x7F000000) == 0)

char* line_code[1000];

struct instruction
{
	instruction() {
		u.pointer = 0;
		u.num = 0;
	}
	char opcode;
	union {
		number num;
		int pointer;
	}u;
	
};

#define TYPE_NUMBER 1
#define TYPE_CODE 2
#define TYPE_C_FUNCTION 3

struct type;

typedef number (*c_function) (int param_num,const type* user_stack);

struct type
{
	char tt;
	union {
		number num;
		int pointer;
		c_function func;
	}u;
	type(number num){
		tt = TYPE_NUMBER;
		u.num = num;
	}
	type(int pointer) {
		tt = TYPE_CODE;
		u.pointer = pointer;
	}
	type(c_function func) {
		tt = TYPE_C_FUNCTION;
		u.func = func;
	}
	type() {
		tt = TYPE_CODE;
		u.pointer = 0;
	}
};



struct machine
{
	char* code;
	char* string_array;
	unsigned int pc;
	unsigned int code_length;
	void* global_table;
	
};

struct running_machine
{
	const instruction* code;
	const char* string_array;
	unsigned int pc;
	const unsigned int code_length;
	void* global_table;
};

#define PUSHNUM 0x1
#define POP 0x2
#define GETLOCAL 0x3
#define SETLOCAL 0x4
#define GETGLOBAL 0x5
#define SETGLOBAL 0x6
#define CALL 0x7
#define RET 0x8
#define CMP 0x9 
#define JUMP 0xA //pc relative jumping
#define JUMPA 0xB
#define ADJLOCAL 0xC
#define NOT 0xD
#define ARITH 0xE
#define PSEUDO_BREAK 0x61
#define PSEUDO_CONTINUE 0x62

#define ARITH_ADD 1
#define ARITH_SUB 2
#define ARITH_MUL 3
#define ARITH_DIV 4


#define COMPARE_LESS 1
#define COMPARE_EQUAL 2
#define COMPARE_GREATER 4

struct less_str
	: public binary_function<const char*,const char*, bool>
{	
bool operator()(const char* const _Left, const char* const _Right) const
	{	
		return (strcmp(_Left,_Right)<0);
	}
};

typedef map<const char*,type,less_str> global_map;

#define new_instruction		memcpy(buffer+pos*sizeof(instruction),&ins,sizeof(instruction)); pos++


//Code generation

class statement {
public:
	virtual int getInstruction(char* buffer) = 0;
	virtual ~statement () {}
};

class expression {
public:
	virtual int getInstruction(char* buffer) = 0;
	virtual ~expression() {}
};

class exp_compare 
	:public expression
{
public:
	exp_compare(int line,expression* left,expression* right,char compare_mode)
		:_line(line),_left(left),_right(right),_compare_mode(compare_mode){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		pos += _left->getInstruction(buffer+pos*sizeof(instruction));
		pos += _right->getInstruction(buffer+pos*sizeof(instruction));
		ins.opcode = CMP;
		ins.u.pointer = _compare_mode;
		new_instruction;
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~exp_compare()
	{
		delete _left;
		delete _right;
	}
private:
	int _line;
	expression* _left;
	expression* _right;
	char _compare_mode;
};

class exp_not
	:public expression
{
public:
	exp_not(int line,expression* cond)
		:_line(line),_cond(cond){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		pos += _cond->getInstruction(buffer);
		ins.opcode = NOT;
		new_instruction;
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~exp_not() { delete _cond; }
private:
	int _line;
	expression* _cond;
};

class exp_and
	:public expression
{
public:
	exp_and(int line,expression* cond1,expression* cond2)
		:_line(line),_cond1(cond1),_cond2(cond2){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		pos += _cond1->getInstruction(buffer);
		// skip cond2 if cond1 not true
		ins.opcode = JUMP;
		ins.u.pointer = 3;
		new_instruction;
		ins.opcode = PUSHNUM;
		ins.u.num = 0;
		new_instruction;
		ins.opcode = JUMPA;
		ins.u.pointer = _cond2->getInstruction(buffer + (pos+1) * sizeof(instruction)) + 1;
		new_instruction;
		pos += (ins.u.pointer-1);
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~exp_and() { delete _cond1; delete _cond2; }
private:
	int _line;
	expression* _cond1;
	expression* _cond2;
};


class exp_or
	:public expression
{
public:
	exp_or(int line,expression* cond1,expression* cond2)
		:_line(line),_exp_ (new exp_not(line, 
		new exp_and(line, new exp_not(line,cond1),new exp_not(line,cond2)
		))){}
	virtual int getInstruction(char* buffer)
	{
		int pos = _exp_->getInstruction(buffer);	
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~exp_or() { delete _exp_; }
private:
	int _line;
	expression* _exp_;
};


class stat_nop 
	:public statement
{
public:
	virtual int getInstruction(char* buffer) {
		return 0;
	}
};

class stat_exp
	:public statement
{
public:
	stat_exp(int line,expression* exp) 
		:_line(line),_exp(exp){}
	virtual int getInstruction(char* buffer) {
		int pos = 0;
		pos += _exp->getInstruction(buffer + pos*sizeof(instruction));
		instruction ins;
		ins.opcode = POP;
		ins.u.pointer = 1;
		new_instruction;
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~stat_exp() { delete _exp; }
private:
	int _line;
	expression* _exp;
};

class stat_seq 
	:public statement
{
public:
	stat_seq(int line,statement** exp_list,int n)
		:_line(line),_exp_list(exp_list),_n(n){}
	virtual int getInstruction(char* buffer) 
	{
		int pos = 0;
		for(int i=0;i<_n;++i) {
			pos += _exp_list[i]->getInstruction(buffer + pos*sizeof(instruction));
		}
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~stat_seq()
	{
		for(int i=0;i<_n;++i) {
			delete _exp_list[i];
		}
		delete [] _exp_list;
	}
private:
	int _line;
	statement** _exp_list;
	int _n;
};

class exp_number 
	:public expression
{
public:
	exp_number(int line,number _n):_line(line),n(_n){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins;
		ins.opcode = PUSHNUM;
		ins.u.num = n;
		memcpy(buffer,&ins,sizeof(instruction));
		line_code[_line] = buffer;
		return 1;
	}
private:
	int _line;
	number n;
};

class exp_var_right
	:public expression
{
public:
	exp_var_right(int line,unsigned int var_name):_line(line),_var(var_name){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins;
		ins.opcode = GETGLOBAL;
		ins.u.pointer = _var;
		memcpy(buffer,&ins,sizeof(instruction));
		line_code[_line] = buffer;
		return 1;
	}
private:
	int _line;
	unsigned int _var;
};

class exp_var_right_local
	:public expression
{
public:
	exp_var_right_local(int line,unsigned int var_name):_line(line),_var(var_name){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins;
		ins.opcode = GETLOCAL;
		ins.u.pointer = _var;
		memcpy(buffer,&ins,sizeof(instruction));
		line_code[_line] = buffer;
		return 1;
	}
private:
	int _line;
	unsigned int _var;
};

class exp_arith
	:public expression
{
public:
	exp_arith(int line,expression* left,expression* right,char mode)
	:_line(line),_left(left),_right(right),_mode(mode){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		pos += _left->getInstruction(buffer+pos*sizeof(instruction));
		pos += _right->getInstruction(buffer+pos*sizeof(instruction));
		ins.opcode = ARITH;
		ins.u.pointer = _mode;
		new_instruction;
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~exp_arith() { delete _left; delete _right; }
private:
	int _line;
	expression* _left;
	expression* _right;
	char _mode;
};

class exp_functioncall
	:public expression
{
public:
	exp_functioncall(int line,unsigned int function_name,expression** exp_list,int exp_num)
		:_line(line),_func(function_name),_exp_list(exp_list),_exp_num(exp_num){}
	virtual int getInstruction(char* buffer)
	{
		int i; int pos = 0;
		for (i = 0;i < _exp_num; ++i)
			pos += _exp_list[i]->getInstruction(buffer+pos*sizeof(instruction));
		instruction ins;
		
		ins.u.pointer = _func;

		ins.opcode = GETGLOBAL;
		new_instruction;

		ins.opcode = CALL;
		ins.u.pointer = _exp_num;
		new_instruction;

		line_code[_line] = buffer;
		return pos;
	}
	virtual ~exp_functioncall()
	{
		for(int i=0;i<_exp_num;++i) {
			delete _exp_list[i];
		}
		delete [] _exp_list;
	}
private:
	int _line;
	unsigned int _func;
	expression** _exp_list;
	int _exp_num;
};

class stat_return
	:public statement
{
public:
	stat_return(int line,expression* exp)
		:_line(line),_exp(exp){}
	virtual int getInstruction(char* buffer) 
	{
		instruction ins; int pos = 0;
		pos += _exp->getInstruction(buffer+pos*sizeof(instruction));
		ins.opcode = RET;
		new_instruction;
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~stat_return() { delete _exp; }
private:
	int _line;
	expression* _exp;
};

class stat_assignment
	:public statement
{
public:
	stat_assignment(int line,unsigned int var_name,expression* exp)
		:_line(line),_var(var_name),_exp(exp){}
	virtual int getInstruction(char* buffer) 
	{
		instruction ins; int pos = 0;
		pos += _exp->getInstruction(buffer+pos*sizeof(instruction));
		ins.opcode = SETGLOBAL;
		ins.u.pointer = _var;
		new_instruction;
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~stat_assignment() { delete _exp; }
private:
	int _line;
	unsigned int _var;
	expression* _exp;
};

class stat_assignment_local
	:public statement
{
public:
	stat_assignment_local(int line,unsigned int var_name,expression* exp)
		:_line(line),_var(var_name),_exp(exp){}
	virtual int getInstruction(char* buffer) 
	{
		instruction ins; int pos = 0;
		pos += _exp->getInstruction(buffer+pos*sizeof(instruction));
		ins.opcode = SETLOCAL;
		ins.u.pointer = _var;
		new_instruction;
		line_code[_line] = buffer;
		return pos;
	}
	virtual ~stat_assignment_local() { delete _exp; }
private:
	int _line;
	unsigned int _var;
	expression* _exp;
};

class stat_if
	:public statement
{
public:
	stat_if(int line,expression* cond,/*cond*/
		statement* do_if_true,statement* do_if_false)
		:_line(line),_cond(cond),_do_if_true(do_if_true),_do_if_false(do_if_false){}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		pos += _cond->getInstruction(buffer);
		int action_if_true_pos = pos + 1 + _do_if_false->getInstruction(buffer+(pos+1)*sizeof(instruction));
		ins.opcode = JUMP;
		ins.u.pointer = action_if_true_pos - pos + 1;
		new_instruction;
		pos = action_if_true_pos;
		int end_pos = pos + 1 + _do_if_true->getInstruction(buffer+(pos+1)*sizeof(instruction));
		ins.opcode = JUMPA;
		ins.u.pointer = end_pos - pos;
		new_instruction;
		line_code[_line] = buffer;
		return end_pos;
	}
	virtual ~stat_if() { delete _cond; delete _do_if_true; delete _do_if_false;}
private:
	int _line;
	expression* _cond;
	statement* _do_if_true;
	statement* _do_if_false;
};

class stat_while
	:public statement
{
public:
	stat_while(int line,expression* cond, /*cond*/
		statement* body)
		:_line(line),_cond(new exp_not(line,cond)),_body(body)
	{

	}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		pos += _cond->getInstruction(buffer);
		int body_length = _body->getInstruction(buffer+(pos+1)*sizeof(instruction));
		//jump to end if false
		ins.opcode = JUMP;
		ins.u.pointer = body_length + 2;
		new_instruction;
		pos += body_length;

		ins.opcode = JUMPA;
		ins.u.pointer = -pos;
		new_instruction;

		//Scan any break and continue instructions
		instruction * insPtr = (instruction*)buffer;
		for (int i=0; i<pos;++i)
		{
			if (insPtr->opcode == PSEUDO_BREAK)
			{
				insPtr->opcode = JUMPA;
				insPtr->u.pointer = pos - i;
			} else if (insPtr->opcode == PSEUDO_CONTINUE)
			{
				insPtr->opcode = JUMPA;
				insPtr->u.pointer = -i;
			}
			
			insPtr++;
		}

		line_code[_line] = buffer;
		return pos;
	}
	virtual ~stat_while() { delete _cond; delete _body; }
private:
	int _line;
	expression* _cond;
	char _compare_mode;
	statement* _body;
};

class stat_break
	:public statement
{
public:
	stat_break(int line)
		:_line(line) {}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		ins.opcode = PSEUDO_BREAK;
		new_instruction;
		return pos;
	}
private:
	int _line;
};

class stat_continue
	:public statement
{
public:
	stat_continue(int line)
		:_line(line) {}
	virtual int getInstruction(char* buffer)
	{
		instruction ins; int pos = 0;
		ins.opcode = PSEUDO_CONTINUE;
		new_instruction;
		return pos;
	}
private:
	int _line;
};

//Execution

int check_string_table(char* string_table,const char* to_find,bool add)
{
	char* p = string_table;
	while(*p) 
	{
		if (strcmp(p,to_find) == 0)
			return p - string_table;
		else
			p = p + strlen(p) + 1;
	}
	if (add) {
		strcpy(p,to_find);
		*(p + strlen(to_find) + 1) = 0;
		return p - string_table;
	} else
		return -1;
}


char* new_zeros(size_t num)
{
	char* s = (char*)malloc(num);
	memset(s,0,num);
	return s;
}

#ifdef NDEBUG
#define ENSURE(cond) (void)( (!!(cond)) || (exit(0), 0) )
#else
#define ENSURE(cond) assert(cond)
#endif

type get_global(running_machine* m,const char* name)
{
	auto it = ((global_map*)m->global_table)->find(name);
	ENSURE(it!=((global_map*)m->global_table)->end());
	return it->second;
}

void set_global(running_machine* m,const char* name,type var)
{
	auto it = ((global_map*)m->global_table)->find(name);
	if (it!=((global_map*)m->global_table)->end())
		it->second = var;
	else
	{
		char* str = new char[256];
		strcpy(str,name);
		((global_map*)m->global_table)->insert(make_pair<const char*,type>(str,var));
	}
}

void free_globals(running_machine* m)
{
	for(auto it = ((global_map*)m->global_table)->begin() ; it != ((global_map*)m->global_table)->end(); ++it)
		delete[] it->first;
	((global_map*)m->global_table)->clear();
}

void print_ins(const instruction* p_ins,int i,running_machine* m)
{
	switch(p_ins->opcode)
	{
	case PUSHNUM:
		printf("%d PUSHNUM %f",i,p_ins->u.num);
		break;
	case POP:
		printf("%d POP %d",i,p_ins->u.pointer);
		break;
	case GETLOCAL:
		printf("%d GETLOCAL %d",i,p_ins->u.pointer);
		break;
	case SETLOCAL:
		printf("%d SETLOCAL %d",i,p_ins->u.pointer);
		break;
	case GETGLOBAL:
		printf("%d GETGLOBAL %s",i,m->string_array + p_ins->u.pointer);
		break;
	case SETGLOBAL:
		printf("%d SETGLOBAL %s",i,m->string_array + p_ins->u.pointer);
		break;
	case CALL:
		printf("%d CALL %d",i,p_ins->u.pointer);
		break;
	case RET:
		printf("%d RET",i);
		break;
	case CMP:
		printf("%d CMP %d",i,p_ins->u.pointer);
		break;
	case JUMP:
		printf("%d JUMP %d",i,p_ins->u.pointer);
		break;
	case JUMPA:
		printf("%d JUMPA %d",i,p_ins->u.pointer);
		break;
	case ADJLOCAL:
		printf("%d ADJLOCAL %d",i,p_ins->u.pointer);
		break;
	case NOT:
		printf("%d NOT",i);
		break;
	case ARITH:
		printf("%d ARITH %d",i,p_ins->u.pointer);
		break;
	default:
		printf("<Unknown instruction>");
		break;
	}
	printf("\n");
}

void execute(running_machine* m)
{
#define STACK_SIZE 65535
	type* user_stack = (type*)new_zeros(sizeof(type)*STACK_SIZE);
	unsigned int* system_stack = (unsigned int*)new_zeros(sizeof(unsigned int)*STACK_SIZE);
	type* user_stack_top = user_stack;
	unsigned int* system_stack_top = system_stack;
#define PUSH_S(stack_top,elem) *stack_top = elem; ++ stack_top;
#define POP_S(stack_top) -- stack_top;

	bool cmp_state;
	type t;
	int n;
	number num;

	while (m->pc < m->code_length)
	{
		const instruction* ins = &m->code[m->pc];
		//print_ins(ins,m->pc,m);
		switch(ins->opcode)
		{
		case PUSHNUM:
			PUSH_S(user_stack_top,type(ins->u.num));
			break;
		case POP:
			for (int i=0;i<ins->u.pointer;++i)
			{
				POP_S(user_stack_top);
			}
			break;
		case GETLOCAL:
			t = user_stack[ins->u.pointer - 1];
			PUSH_S(user_stack_top,t);
			break;
		case SETLOCAL:
			user_stack[ins->u.pointer - 1] = *(user_stack_top - 1);
			POP_S(user_stack_top);
			break;
		case GETGLOBAL:
			PUSH_S(user_stack_top,get_global(m,m->string_array+ins->u.pointer));
			break;
		case SETGLOBAL:
			set_global(m,m->string_array+ins->u.pointer,*(user_stack_top - 1));
			POP_S(user_stack_top);
			break;
		case CALL:
			PUSH_S(system_stack_top,m->pc);
			PUSH_S(system_stack_top,(unsigned int)user_stack);
			t = *(user_stack_top - 1); // new_address
			POP_S(user_stack_top);
			user_stack = user_stack_top - ins->u.pointer;
			if (t.tt == TYPE_CODE)
			{
				m->pc = t.u.pointer;
				continue;
			} else 
			{
				//C function
				PUSH_S(user_stack_top,type(t.u.func(ins->u.pointer,user_stack)));
				// Fall through to RET 
			}
		case RET:
			if (system_stack_top == system_stack)
				goto ret;
			t = *(user_stack_top - 1); //retval
			user_stack_top = user_stack;
			user_stack = (type*)*(--system_stack_top);
			m->pc = *(--system_stack_top);
			PUSH_S(user_stack_top,t);
			break;
		case CMP:
			type* right; right = user_stack_top - 1;
			type* left; left = user_stack_top - 2;
						
			ENSURE(left->tt == TYPE_NUMBER && right->tt == TYPE_NUMBER);
			num = left->u.num - right->u.num;
			if ( double_zero(num) )
			{
				cmp_state = (ins->u.pointer & COMPARE_EQUAL);
			} else
			{
				if (num < 0)
					cmp_state = (ins->u.pointer & COMPARE_LESS);
				else
					cmp_state = (ins->u.pointer & COMPARE_GREATER);
			}
			POP_S(user_stack_top);
			//POP_S(user_stack_top);
			if (cmp_state)
			{
				//PUSH_S(user_stack_top,type(1.0));
				left->u.num = 1.0;
			}
			else
			{
				//PUSH_S(user_stack_top,type(0.0));
				left->u.num = 0.0;
			}
			break;
		case JUMP:
			ENSURE((user_stack_top-1)->tt == TYPE_NUMBER);
			//cmp_state = !(abs((user_stack_top-1)->u.num) < 0.000001);
			cmp_state = !double_zero((user_stack_top-1)->u.num);
			POP_S(user_stack_top);
			if (!cmp_state)
				break;
		case JUMPA:
			m->pc += ins->u.pointer;
			continue;
		case ADJLOCAL:
			n = user_stack_top - user_stack;
			while(n > ins->u.pointer)
			{
				POP_S(user_stack_top);
				--n;
			}
			while(n < ins->u.pointer)
			{
				PUSH_S(user_stack_top,type(0));
				++n;
			}
			break;
		case NOT:
			ENSURE((user_stack_top-1)->tt == TYPE_NUMBER);
			if  ( double_zero((user_stack_top-1)->u.num)  )
			{
				assert( abs((user_stack_top-1)->u.num) < 0.000001 );
				(user_stack_top-1)->u.num = 1;
			}
			else
				(user_stack_top-1)->u.num = 0;
			break;
		case ARITH:
			ENSURE((user_stack_top-1)->tt == TYPE_NUMBER && (user_stack_top-2)->tt == TYPE_NUMBER);
			switch (ins->u.pointer)
			{
			case ARITH_ADD:
				num = (user_stack_top-2)->u.num + (user_stack_top-1)->u.num;
				break;
			case ARITH_SUB:
				num = (user_stack_top-2)->u.num - (user_stack_top-1)->u.num;
				break;
			case ARITH_MUL:
				num = (user_stack_top-2)->u.num * (user_stack_top-1)->u.num;
				break;
			case ARITH_DIV:
				num = (user_stack_top-2)->u.num / (user_stack_top-1)->u.num;
				break;
			default:
				ENSURE(0 && "Unknown arith type");
			}
			POP_S(user_stack_top);
			//POP_S(user_stack_top);
			//PUSH_S(user_stack_top,type(num));
			(user_stack_top-1)->u.num = num;
			break;
		case PSEUDO_BREAK:
		case PSEUDO_CONTINUE:
			ENSURE(0 && "Unexpected break or continue outside while loop");
			break;
		default:
			ENSURE(0 && "Unknown instruction");
			break;
		}
		++m->pc;
	}
ret:
	free(user_stack);
	free(system_stack);
	return;
}


number __print(int param_num,const type* user_stack)
{
	for( int i = 0;i < param_num ;++i)
	{
		ENSURE(user_stack[i].tt == TYPE_NUMBER);
		printf("%f",user_stack[i].u.num);
		if (i != param_num - 1)
			printf("\t");
	}
	printf("\n");
	return 0;
}


//Parser

#define TOKEN_IF 0x101
#define TOKEN_ELSE 0x102
#define TOKEN_WHILE 0x103
#define TOKEN_FUNCTION 0x104
#define TOKEN_NUMBER 0x105
#define TOKEN_ID 0x106
#define TOKEN_EQUAL 0x107
#define TOKEN_GEQ 0x108
#define TOKEN_LEQ 0x109
#define TOKEN_NEQU 0x110
#define TOKEN_RETURN 0x111
#define TOKEN_LOCAL 0x112
#define TOKEN_LOGICAL_AND 0x113
#define TOKEN_LOGICAL_OR 0x114
#define TOKEN_BREAK 0x115
#define TOKEN_CONTINUE 0x116

const char * getTokenName(short tt)
{
	static char buf[2];
	switch(tt)
	{
	case TOKEN_IF:
		return "TOKEN_IF";
	case TOKEN_ELSE:
		return "TOKEN_ELSE";
	case TOKEN_WHILE:
		return "TOKEN_WHILE";
	case TOKEN_FUNCTION:
		return "TOKEN_FUNCTION";
	case TOKEN_NUMBER:
		return "TOKEN_NUMBER";
	case TOKEN_ID:
		return "TOKEN_ID";
	case TOKEN_EQUAL:
		return "TOKEN_EQUAL";
	case TOKEN_GEQ:
		return "TOKEN_GEQ";
	case TOKEN_LEQ:
		return "TOKEN_LEQ";
	case TOKEN_NEQU:
		return "TOKEN_NEQU";
	case TOKEN_RETURN:
		return "TOKEN_RETURN";
	case TOKEN_LOCAL:
		return "TOKEN_LOCAL";
	case TOKEN_LOGICAL_AND:
		return "TOKEN_LOGICAL_AND";
	case TOKEN_LOGICAL_OR:
		return "TOKEN_LOGICAL_OR";
	case TOKEN_BREAK:
		return "TOKEN_BREAK";
	case TOKEN_CONTINUE:
		return "TOKEN_CONTINUE";
	default:
		*buf = (char)tt;
		buf[1] = 0;
		return buf;
	}
}

// if else while function return local
// () {} + - * / > >= < <= = == <> `
/*
argsopt-> e | args
args -> args,expr | expr
parmopt-> e | params
params-> id | params,id
function_call -> id(argsopt)
factor-> number | function_call | (expr) | !expr
term -> term * factor | term / factor | factor
expr -> expr + term | expr - term | term
compare -> expr > expr | expr==expr | expr<expr | expr<=expr | expr>=expr | expr!=expr | expr | (cond)
cond -> cond && compare | cond || compare | !compare
stmt -> expr; | id=expr; | if(cond)stmt [else stmt] | while(cond)stmt | return expr | {stmts} | local params
stmts -> stmts stmt | e
function_def -> function id(parmopt)stmt
*/
struct token
{
	short tt;
	union {
		char* ident;
		number num;
	}u;
};

static short priorities [][7] = 
{
	{'*','/',-1},
	{'+','-',-1},
	{'>','<',TOKEN_EQUAL,TOKEN_GEQ,TOKEN_LEQ,TOKEN_NEQU,-1},
	{TOKEN_LOGICAL_AND,-1 },
	{TOKEN_LOGICAL_OR,-1},
};

struct function_context
{
	char name[256];
	char* locals[256];
};
function_context* current = NULL;

struct lex_state;
token look_ahead;

token next(lex_state* l);
int current_line(lex_state* l);

int check_local(char* name,bool add)
{
	int i=0;
	while(current->locals[i])
	{
		if (strcmp(name,current->locals[i]) == 0)
			return i+1;
		i++;
	}
	if (add)
	{
		current->locals[i] = new char[256];
		strcpy(current->locals[i],name);
		return i+1;
	}
	return -1;
}

void free_local()
{
	int i=0;
	while(current->locals[i])
	{
		delete current->locals[i];
		i++;
	}
	delete current;
	current = NULL;
}

void accept(lex_state* l)
{
	look_ahead = next(l);
}

token match(lex_state* l,int token_type)
{
	token retval = look_ahead;
	if (look_ahead.tt == token_type)
		accept(l);
	else
	{
		printf("expect symbol %s near %s",getTokenName(token_type),getTokenName(look_ahead.tt));
		//__asm int 3;
		exit(0);
	}
	return retval;
}

expression* expr(lex_state* l,machine* m);

void params(lex_state* l,machine* m,bool locals)
{
	char eod = ')';
	if (locals)
		eod = ';';
	while(look_ahead.tt!=eod)
	{
		token id = match(l,TOKEN_ID);
		check_local(id.u.ident,true);
		if (look_ahead.tt!=eod)
			match(l,',');
	}
}

expression** args(lex_state* l,machine* m,int* exp_num)
{
	*exp_num = 0;
	expression** el = new expression*[10000];
	while(look_ahead.tt!=')')
	{
		el[*exp_num] = expr(l,m);
		(*exp_num)++;
		if (look_ahead.tt!=')')
			match(l,',');
	}
	return el;
}

expression* factor(lex_state* l,machine* m)
{
	expression* retval;
	int local;int global;
	token id;
	switch(look_ahead.tt)
	{
	case '(':
		accept(l);retval = expr(l,m); match(l,')');
		break;
	case TOKEN_ID:
		id = match(l,TOKEN_ID);
		local =  check_local(id.u.ident,false);
		if (local == -1 || look_ahead.tt == '(')
			global = check_string_table(m->string_array,id.u.ident,true);
		if (look_ahead.tt == '(') //function call
		{
			int exp_num = 0;int line = current_line(l);
			accept(l);expression** argss = args(l,m,&exp_num);match(l,')');
			retval = new exp_functioncall(line,global,argss,exp_num);
		}
		else
		{
			if (local != -1)
				retval = new exp_var_right_local(current_line(l),local);
			else
				retval = new exp_var_right(current_line(l),global);
		}
		break;
	case TOKEN_NUMBER:
		id = match(l,TOKEN_NUMBER);
		return new exp_number(current_line(l),id.u.num);
	case '!':
		accept(l);
		return new exp_not(current_line(l),factor(l,m));
	default:
		printf("unexpected symbol %c\n",look_ahead.tt);
		//__asm int 3
		exit(0);
	}
	return retval;
}

bool in_priority(short tt,int priority)
{
	int i=0;
	while(priorities[priority][i] != -1)
	{
		if (priorities[priority][i] == tt) return true;
		++i;
	}
	return false;
}

char get_compare_mode(lex_state* l)
{
	switch(look_ahead.tt)
	{
		case '<':
			return COMPARE_LESS;
		case '>':
			return COMPARE_GREATER;
			break;
		case TOKEN_GEQ:
			return COMPARE_GREATER | COMPARE_EQUAL;
		case TOKEN_EQUAL:
			return COMPARE_EQUAL;
		case TOKEN_LEQ:
			return COMPARE_LESS | COMPARE_EQUAL;
		case TOKEN_NEQU:
			return COMPARE_GREATER | COMPARE_LESS;
	};
	return 0;
}

expression* expr1(lex_state* l,machine* m,int priority)
{
	expression* retval;
	expression* right;
	int func;
	expression** list;
	char compare_mode;
	int line = current_line(l);
	if (priority >= 0)
		retval = expr1(l,m,priority - 1);
	else
		return factor(l,m);
	while (in_priority(look_ahead.tt,priority))
	{
		switch(look_ahead.tt)
		{
		case '+':
			accept(l);
			right = expr1(l,m,priority-1);
			retval = new exp_arith(line,retval,right,ARITH_ADD);
			break;
		case '-':
			accept(l);
			right = expr1(l,m,priority-1);
			retval = new exp_arith(line,retval,right,ARITH_SUB);
			break;
		case '*':
			accept(l);
			right = expr1(l,m,priority-1);
			retval = new exp_arith(line,retval,right,ARITH_MUL);
			break;
		case '/':
			accept(l);
			right = expr1(l,m,priority-1);
			retval = new exp_arith(line,retval,right,ARITH_DIV);
			break;
		case '<':
		case '>':
		case TOKEN_GEQ:
		case TOKEN_EQUAL:
		case TOKEN_LEQ:
		case TOKEN_NEQU:
			compare_mode = get_compare_mode(l);
			accept(l);
			right = expr1(l,m,priority-1);
			retval = new exp_compare(line,retval,right,compare_mode);
			break;
		case TOKEN_LOGICAL_AND:
			accept(l);
			right = expr1(l,m,priority-1);
			retval = new exp_and(line,retval,right);
			break;
		case TOKEN_LOGICAL_OR:
			accept(l);
			right = expr1(l,m,priority-1);
			retval = new exp_or(line,retval,right);
			break;
		default:
			return retval;
		}
		
	}
	
	return retval;
}

expression* expr(lex_state* l,machine* m)
{
	return expr1(l,m,4);
}

statement* stmt(lex_state* l,machine* m);
statement* stmts(lex_state* l,machine* m)
{
	statement** sl = new statement*[1000]; int nl = 0;
	int line = current_line(l);
	while(look_ahead.tt!='}')
	{
		statement* s = stmt(l,m);
		sl[nl++] = s;
	}
	return new stat_seq(line,sl,nl);
}
statement* stmt(lex_state* l,machine* m)
{
	statement* retval;
	statement* do_if_true;
	statement* do_if_false;
	expression* cmp;
	int local;
	int global;
	token id;
	int exp_num = 0;
	int line = current_line(l);
	switch(look_ahead.tt)
	{
	case '{':
		match(l,'{');
		retval = stmts(l,m);
		match(l,'}');
		break;
	case TOKEN_IF:
		match(l,TOKEN_IF);match(l,'(');
		cmp = expr(l,m);
		match(l,')');
		do_if_true = stmt(l,m);
		if (look_ahead.tt == TOKEN_ELSE)
		{
			accept(l);
			do_if_false = stmt(l,m);
		}
		else
			do_if_false = new stat_nop();
		retval = new stat_if(line,cmp,do_if_true,do_if_false);
		break;
	case TOKEN_WHILE:
		match(l,TOKEN_WHILE);match(l,'(');
		cmp = expr(l,m);
		match(l,')');
		retval = new stat_while(line,cmp,stmt(l,m));
		break;
	case TOKEN_ID:
		id = match(l,TOKEN_ID);
		local =  check_local(id.u.ident,false);
			if (local == -1 || look_ahead.tt == '(')
				global = check_string_table(m->string_array,id.u.ident,true);
		if (look_ahead.tt == '(') // function call
		{
			exp_num = 0;
			accept(l);expression** argss = args(l,m,&exp_num);match(l,')');
			retval = new stat_exp(line,new exp_functioncall(line,global,argss,exp_num) );
		}
		else
		{
			match(l,'=');
			if (local != -1)
				retval = new stat_assignment_local(line,local,expr(l,m));
			else
				retval = new stat_assignment(line,global,expr(l,m));
		}
		match(l,';');
		break;
	case TOKEN_RETURN:
		accept(l);
		retval = new stat_return(line,expr(l,m));
		match(l,';');
		break;
	case TOKEN_LOCAL:
		accept(l);
		params(l,m,true);
		match(l,';');
		retval = new stat_nop();
		break;
	case TOKEN_BREAK:
		accept(l);
		retval = new stat_break(line);
		match(l,';');
		break;
	case TOKEN_CONTINUE:
		accept(l);
		retval = new stat_continue(line);
		match(l,';');
		break;
	default:
		retval = new stat_exp(line,expr(l,m));
		match(l,';');
	}
	return retval;
}
statement* function_def(lex_state* l,machine* m)
{
	match(l,TOKEN_FUNCTION);
	token id = match(l,TOKEN_ID);
	if (current) 
		delete current;
	current = new function_context;
	for(int i=0;i<256;++i)
		current->locals[i] = 0;
	strcpy(current->name,id.u.ident);
	match(l,'(');params(l,m,false);match(l,')');
	return stmt(l,m);
}

//Lexer

struct lex_state
{
	char buffer[256];
	int n;
	FILE* fp;
	char current;
	token last;
	int line;
	bool eof;
	bool comment;
};

int current_line(lex_state* l)
{
	return l->line;
}

void parse(lex_state* l,machine* m)
{
	int pos = 0;
	int nlocals = 0;
	accept(l);
	instruction ins;
	char* buffer = m->code;
	while(!l->eof)
	{
		statement* function = function_def(l,m);
		set_global((running_machine*)m,current->name,type(pos));
		nlocals = 0;
		for(int i=0;;++i,++nlocals)
		{
			if (!current->locals[i])break;
		}
		ins.opcode = ADJLOCAL;
		ins.u.pointer = nlocals;
		new_instruction;
		pos += function->getInstruction(m->code+pos*sizeof(instruction));
		ins.opcode = RET;
		new_instruction;
		delete function;
		free_local();
	}
	m->code_length = pos;
	
}


#define next_char(l) {fread(&l->current ,1,1,l->fp); if(feof(l->fp))l->eof = true;}
lex_state* lex_new(const char* file)
{
	lex_state* lex = new lex_state;
	memset(lex,0,sizeof(lex_state));
	lex->fp = fopen(file,"r");
	lex->line = 1;
	ENSURE(lex->fp != NULL);
	next_char(lex);
	return lex;
}

number read_number(lex_state* l)
{
	double d = 0;
	double t = 1;
	do
	{
		d *= 10;
		d = d + (l->current - '0');
		next_char(l);
	}while(isdigit(l->current));
	if (l->current == '.')
	{
		next_char(l);
		while (isdigit(l->current))
		{
			t /= 10;
			d += t * (l->current - '0');
			next_char(l);
		}
	}
	return d;
}
#define ret_token(l,tok) l->last = tok; return tok
// if else while function
// () {} + - * / > >= < <= = == !=
token next(lex_state* l)
{	
	while(l->current == ' ' || l->current == '\t')
	{
		next_char(l);
	}
	token t;
	while (!l->eof) {
		if (l->comment)
		{
			next_char(l);
			if (l->current != '\r' && l->current != '\n')
				continue;
		}
		switch(l->current)
		{
			case '\r':
			case '\n':
				l->line ++;
				l->comment = false;
				next_char(l);
				break;
			case '`':
				l->comment = true;
				next_char(l);
				break;
			case '-':
				if (l->last.tt != TOKEN_ID && l->last.tt != TOKEN_NUMBER && l->last.tt  != ')') {
					t.tt = TOKEN_NUMBER;
					t.u.num = 0;
					ret_token(l,t);
				} else {
					t.tt = '-';
					next_char(l);
					ret_token(l,t);
				}
			case '!':
				t.tt = l->current;
				next_char(l);				
				if (l->current == '=')
				{
					t.tt = TOKEN_NEQU;
					next_char(l);
				}
				ret_token(l,t);
			case '>':
				t.tt = l->current;
				next_char(l);				
				if (l->current == '=')
				{
					t.tt = TOKEN_GEQ;
					next_char(l);
				}
				ret_token(l,t);
			case '<':
				t.tt = l->current;
				next_char(l);
				if (l->current == '=')
				{
					t.tt = TOKEN_LEQ;
					next_char(l);
				} else if (l->current == '>')
				{
					t.tt = TOKEN_NEQU;
					next_char(l);
				}
				ret_token(l,t);
			case '=':
				t.tt = l->current;
				next_char(l);
				if (l->current == '=')
				{
					t.tt = TOKEN_EQUAL;
					next_char(l);
				}
				ret_token(l,t);
			case '&':
				t.tt = l->current;
				next_char(l);
				if(l->current == '&')
				{
					t.tt = TOKEN_LOGICAL_AND;
					next_char(l);
				}
				ret_token(l,t);
			case '|':
				t.tt = l->current;
				next_char(l);
				if(l->current == '|')
				{
					t.tt = TOKEN_LOGICAL_OR;
					next_char(l);
				}
				ret_token(l,t);
			default:
				if (isspace(l->current))
				{
					next_char(l);
					continue;
				}
				if (isdigit(l->current))
				{
					t.tt = TOKEN_NUMBER;
					t.u.num = read_number(l);
					ret_token(l,t);
				}
				if (isalpha(l->current) || l->current == '_') {
					do {
						l->buffer[l->n++] = l->current;
						next_char(l);
					}while(isalnum(l->current) || l->current == '_');
					l->buffer[l->n] = 0;
					l->n = 0;
					if (strcmp(l->buffer,"if") == 0)
						t.tt = TOKEN_IF;
					else if (strcmp(l->buffer,"else") == 0)
						t.tt = TOKEN_ELSE;
					else if (strcmp(l->buffer,"while") == 0)
						t.tt = TOKEN_WHILE;
					else if (strcmp(l->buffer,"function") == 0)
						t.tt = TOKEN_FUNCTION;
					else if (strcmp(l->buffer,"return") == 0)
						t.tt = TOKEN_RETURN;
					else if (strcmp(l->buffer,"local") == 0)
						t.tt = TOKEN_LOCAL;
					else if (strcmp(l->buffer,"break") == 0)
						t.tt = TOKEN_BREAK;
					else if (strcmp(l->buffer,"continue") == 0)
						t.tt = TOKEN_CONTINUE;
					else
					{
						t.tt = TOKEN_ID;
						t.u.ident = l->buffer;
					}
					ret_token(l,t);
				}
				t.tt = l->current;
				next_char(l);
				ret_token(l,t);
		}

	}
	t.tt = 0;
	return t;
}



int main(int argc,char** argv)
{
		
		machine m; m.pc = 0;
		m.string_array = new_zeros(65536);
		m.code = new_zeros(65536);

		m.global_table = new global_map;
		
		set_global((running_machine*)&m,"print",type(__print));


		lex_state* l;
		if (argc > 1)
			l = lex_new(argv[1]);
		else
			l = lex_new("script.txt");
		parse(l,&m);
		delete l;

		instruction* p_ins = (instruction*)m.code;

		for( int i=0;i<m.code_length;++i)
		{
			print_ins(p_ins,i,(running_machine*)&m);
			p_ins++;
		}

		m.pc = get_global((running_machine*)&m,"main").u.pointer;
		execute((running_machine*)&m);

		free(m.string_array);
		free(m.code);
		free_globals((running_machine*)&m);
		delete (global_map*)m.global_table;

		return 0;
}
